package sort.yht;

import sort.util.MySort;

/**
 * 功能描述：归并排序
 * @Author: yht
 * @Date: 2021/8/11 14:12
 */
public class GuiBing implements MySort {

  @Override
  public String getName() {
    return "【归并排序】";
  }

  @Override
  public int[] sort(int[] a) {
    int [] tmp = new int[a.length];
    return doSort(a,0,a.length-1, tmp);
  }

  private int[] doSort(int[] a, int left, int right, int[] tmp) {
    if(right - left > 1) {
      int mid = left + (right - left)/2;
      doSort(a, left, mid, tmp);
      doSort(a, mid+1, right, tmp);
      merge(a, left, mid, right, tmp);
    } else {
      if(a[right] < a[left]) {
        int m = a[right];
        a[right] = a[left];
        a[left] = m;
      }
    }
    return a;
  }

  private void merge(int[] a, int left, int mid, int right, int[] tmp) {
    int i = left, j = mid+1, m=left;
    while (m <= right) {
      if(j > right || (i <= mid && a[i] <= a[j])) {
        tmp[m] = a[i];
        i++;
      }else{
        tmp[m] = a[j];
        j++;
      }
      m++;
    }
    for(int n = left; n <= right; n++ ) {
      a[n] = tmp[n];
    }
  }

  public static void main(String[] args) {
    GuiBing gb = new GuiBing();
    gb.testAll();
  }
}
